# DFS解决所有岛屿问题

# DFS遍历二维数组
def dfs(grid, i, j, visited):
    m = len(grid)
    n = len(grid[0])
    # base case
    if i < 0 or i >= m or j < 0 or j >= n:
        return

    if visited[i][j]: return

    # 前序位置
    visited[i][j] = 1
    # print("当前节点的值为{}".format(grid[i][j]))
    dfs(grid, i-1, j, visited)  # 上
    dfs(grid, i+1, j, visited)  # 下
    dfs(grid, i, j-1, visited)  # 左
    dfs(grid, i, j+1, visited)  # 右

dfs([[1, 2, 3], [4, 5, 6]], 0, 0, [[0, 0, 0], [0, 0, 0]])

# Tips: 使用方向数组遍历
dirs = [[-1, 0], [1, 0], [-1, 0], [0, 1]]
def dfs(grid, i, j, visited):
    m = len(grid)
    n = len(grid[0])
    # base case
    if i < 0 or i >= m or j < 0 or j >= n:
        return

    if visited[i][j]: return

    # 前序位置
    visited[i][j] = 1
    print("当前节点的值为{}".format(grid[i][j]))
    for d in dirs:
        dfs(grid, i+d[0], j+d[1], visited)

dfs([[1, 2, 3], [4, 5, 6]], 0, 0, [[0, 0, 0], [0, 0, 0]])


# L200 岛屿数量1
# 发现一个1,res+=1,再将1的上下左右都用0淹没
def numIslands(grid):
    def dfs(i, j):
        if i < 0 or j < 0 or i >= m or j >= n: return
        if grid[i][j] == "0": return

        # 前序
        str_list = list(grid[i])
        str_list[j] = "0"
        grid[i] = "".join(str_list)

        # 递归
        for dir in dirs:
            dfs(i+dir[0], j+dir[1])

    res = 0
    m = len(grid)
    n = len(grid[0])

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                res += 1
                dfs(i, j)
    return res


grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
print("{}的岛屿数量为{}".format(grid[:], numIslands(grid)))


# L1254封闭岛屿数量 先把边界上的土地都淹没
def closedIsland(grid):
    m = len(grid)
    n = len(grid[0])

    def dfs(i, j):
        if i < 0 or j < 0 or i >= m or j >= n: return
        if grid[i][j] == 1: return

        grid[i][j] = 1

        for dir in dirs:
            dfs(i+dir[0], j+dir[1])

    for i in range(n):
        dfs(0, i)  # 淹没第一行的0
        dfs(m-1, i)  # 淹最后一行的0

    for i in range(m):
        dfs(i, 0)  # 淹没第一列的0
        dfs(i, n-1)  # 淹最后一列的0

    res = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                res += 1
                dfs(i, j)
    return res



# 0是土地 1是水
grid = [[1, 1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0], [1, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 0]]
print("{}的封闭岛屿数量为{}".format(grid[:], closedIsland(grid)))

# L1905 岛屿的最大面积
def maxAreaOfIsland(grid):
    m = len(grid)
    n = len(grid[0])

    def dfs(i, j):  # 递归函数：计算被淹没岛屿的面积并返回
        if i < 0 or j < 0 or i >= m or j >= n: return 0
        if grid[i][j] == 0: return 0

        grid[i][j] = 0

        return dfs(i-1, j)+dfs(i+1, j)+dfs(i, j-1)+dfs(i, j+1)+1

    res = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j]:
                res = max(res, dfs(i, j))

    return res

grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
print("最大面积是{}".format(maxAreaOfIsland(grid)))